Quadratically constrained quadratic program
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
top
In mathematical optimization, a quadratically constrained quadratic program (QCQP) is an optimization problem in which both the objective function and the constraints are quadratic functions. It has the form
minimize 1 2 x T P 0 x + q 0 T x subject to 1 2 x T P i x + q i T x + r i ≤ 0 for i = 1 , … , m , A x = b , {\displaystyle {\begin{aligned}&{\text{minimize}}&&{\tfrac {1}{2}}x^{\mathrm {T} }P_{0}x+q_{0}^{\mathrm {T} }x\\&{\text{subject to}}&&{\tfrac {1}{2}}x^{\mathrm {T} }P_{i}x+q_{i}^{\mathrm {T} }x+r_{i}\leq 0\quad {\text{for }}i=1,\dots ,m,\\&&&Ax=b,\end{aligned}}}
where P0, ..., Pm are n-by-n matrices and x ∈ Rn is the optimization variable.
If P0, ..., Pm are all positive semidefinite, then the problem is convex. If these matrices are neither positive nor negative semidefinite, the problem is non-convex. If P1, ... ,Pm are all zero, then the constraints are in fact linear and the problem is a quadratic program.
Contents
• Hardness
• Example
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
Hardness
A convex QCQP problem can be efficiently solved using an interior point method (in a polynomial time), typically requiring around 30-60 iterations to converge. Solving the general non-convex case is an NP-hard problem.
To see this, note that the two constraints x1(x1 − 1) ≤ 0 and x1(x1 − 1) ≥ 0 are equivalent to the constraint x1(x1 − 1) = 0, which is in turn equivalent to the constraint x1 ∈ {0, 1}. Hence, any 0–1 integer program (in which all variables have to be either 0 or 1) can be formulated as a quadratically constrained quadratic program. Since 0–1 integer programming is NP-hard in general, QCQP is also NP-hard.
However, even for a nonconvex QCQP problem a local solution can generally be found with a nonconvex variant of the interior point method. In some cases (such as when solving nonlinear programming problems with a sequential QCQP approach) these local solutions are sufficiently good to be accepted.
Relaxation
There are two main relaxations of QCQP: using semidefinite programming (SDP), and using the reformulation-linearization technique (RLT). For some classes of QCQP problems (precisely, QCQPs with zero diagonal elements in the data matrices), second-order cone programming (SOCP) and linear programming (LP) relaxations providing the same objective value as the SDP relaxation are available.cite-ref-1[1]
Nonconvex QCQPs with non-positive off-diagonal elements can be exactly solved by the SDP or SOCP relaxations,cite-ref-2[2] and there are polynomial-time-checkable sufficient conditions for SDP relaxations of general QCQPs to be exact.cite-ref-0-3-0[3] Moreover, it was shown that a class of random general QCQPs has exact semidefinite relaxations with high probability as long as the number of constraints grows no faster than a fixed polynomial in the number of variables.cite-ref-0-3-1[3]
Semidefinite programming
When P0, ..., Pm are all positive-definite matrices, the problem is convex and can be readily solved using interior point methods, as done with semidefinite programming.
Example
• Max Cut is a problem in graph theory, which is NP-hard. Given a graph, the problem is to divide the vertices in two sets, so that as many edges as possible go from one set to the other. Max Cut can be formulated as a QCQP, and SDP relaxation of the dual provides good lower bounds.
• QCQP is used to finely tune machine setting in high-precision applications such as photolithography.
Solvers and scripting (programming) languages
| Name | Brief info |
|---|---|
| ALGLIB | ALGLIB, an open source/commercial numer… |
| Artelys Knitro | Knitro is a solver specialized in nonli… |
| FICO Xpress | A commercial optimization solver for li… |
| AMPL | |
| CPLEX | Popular solver with an API for several… |
| MOSEK | A solver for large scale optimization w… |
| TOMLAB | Supports global optimization, integer p… |
| Wolfram Mathematica | Able to solve QCQP type of problems usi… |
| clarabel | Open source interior point numerical so… |
References
cite-note-11. ↑ citerefkimizukakimyamashita2019Kimizuka, Masaki; Kim, Sunyoung; Yamashita, Makoto (2019). "Solving pooling problems with time discretization by LP and SOCP relaxations and rescheduling methods". Journal of Global Optimization. 75 (3): 631–654. doi:10.1007/s10898-019-00795-w. ISSN 0925-5001. S2CID 254701008.
• citerefboydlieven-vandenberghe2004Boyd, Stephen; Lieven Vandenberghe (2004). Convex Optimization. Cambridge: Cambridge University Press. ISBN 978-0-521-83378-3.
Further reading
In statistics
• citerefalbers-c-j-critchley-f-gower-j-c-2011Albers C. J., Critchley F., Gower, J. C. (2011). "Quadratic Minimisation Problems in Statistics" (PDF). Journal of Multivariate Analysis. 102 (3): 698–713. doi:10.1016/j.jmva.2009.12.018. hdl:11370/6295bde7-4de1-48c2-a30b-055eff924f3e.{{cite journal}}: CS1 maint: multiple names: authors list (link)
External links
• NEOS Optimization Guide: Quadratic Constrained Quadratic Programming Archived 2013-04-02 at the Wayback Machine